我也不知道我怎么找到的这题,但是既然 AC 了,就来写一篇题解。
题意简述:共 组询问,每次读入两个数 ,输出 的值,其中 为斐波那契数。
由于洛谷爬的时候漏掉了数据范围,可以到原题目中查看:,可以看到暴力求出所有斐波那契数的前缀和后求解显然会超时,容易想到矩阵加速。
我们使用矩阵维护第 项、第 项的值及前 项的和,下面考虑构造转移矩阵。
根据斐波那契数列的定义,我们知道:
经过一些简单变换即可得到转移矩阵:
此时,我们可以通过类似于题目矩阵加速的方式利用矩阵快速幂在 时间内求出对于一个整数 的 的值。我们要求的答案即为 。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll T, n, m;
struct Matrix {
ll id[4][4];
Matrix() {}
Matrix(int x, int y, int z) {id[1][1]=x;id[1][2]=y;id[1][3]=z;}
~Matrix() {}
void clear() {memset(id, 0, sizeof(id));}
void init(ll k) {clear(); for(ll i=1;i<=k;i++) id[i][i] = 1;}
}a, b;
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
c.clear();
for(ll i=1;i<=3;i++)
for(ll j=1;j<=3;j++)
for(ll k=1;k<=3;k++)
c.id[i][j] = (c.id[i][j] + a.id[i][k] * b.id[k][j] % mod) % mod;
return c;
}
Matrix operator ^ (Matrix &a, ll k) {
Matrix res;
res.init(3);
for(;k;k>>=1,a=a*a) if(k&1) res = res * a;
return res;
}
Matrix calc(ll k) {
if(k <= 0) return Matrix(0, 0, 0);
if(k == 1) return Matrix(0, 1, 1);
if(k == 2) return Matrix(1, 1, 2);
a.clear(); b.clear();
a.id[1][1] = a.id[1][2] = a.id[1][3] = 1;
b.id[1][2] = b.id[2][1] = b.id[2][2] = b.id[2][3] = b.id[3][3] = 1;
a = a * (b ^ (k - 1));
return a;
}
int main() {
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld", &n, &m);
printf("%lld\n", (calc(m).id[1][3]%mod-calc(n-1).id[1][3]%mod+mod)%mod);
}
return 0;
}